﻿// 和可被K整除的⼦数组
// 给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。
// 子数组 是数组中 连续 的部分。

class Solution {
public:
 int subarraysDivByK(vector<int>& nums, int k) 
 {
 unordered_map<int, int> hash;
 hash[0 % k] = 1; // 0 这个数的余数 
 int sum = 0, ret = 0;
 for(auto x : nums)
 {
 sum += x; // 算出当前位置的前缀和 
 int r = (sum % k + k) % k; // 修正后的余数 
 if(hash.count(r)) ret += hash[r]; // 统计结果 
 hash[r]++;
 }
 return ret;
 }
};



